//
// Created by ZYZ on 2020/6/22.
//

#include <stdio.h>
#include <stdlib.h>

#include <iostream>
#include <string>

using namespace std;

#include "binary_tree.h"
#include "../../include/define.h"
#include "../../src/linear_stack/linear_stack.h"
#include "../linked_queue/linked_queue.h"
#include "../../include/type_binary_tree.h"
#include "../../include/type_linked_queue.h"
#include "../common/math.h"

//功能: 创建二叉树
//备注: 前序方式创建
Status CreateBiTree(BiTree &biTree) {
    printf("请输入二叉树结点数据: \n");
//    char ch = getchar();
    char ch;
    scanf(" %c", &ch);                //过滤空白字符
    if ('#' == ch) biTree = NULL;
    else {
        if (!(biTree = (BiTNode *) malloc(sizeof(BiTNode))))
            exit(OVERFLOW);
        biTree->data = ch;                 //生成根结点
        CreateBiTree(biTree->lchild);  //构造左子树
        CreateBiTree(biTree->rchild);  //构造右子树
    }
    return OK;
}

//计算二叉树的最大深度，最大深度指从根节点到叶子节点的最长路径上的节点个数
//对于任意一个节点，它的深度是由它左右两个子节点的深度决定的，即如果左右两个子节点的深度分别为 HL 和 HR，那么当前节点的深度就是 max(HL,HR) + 1
int maxBiTreeDepth(BiTree &root) {
    return root ? max(maxBiTreeDepth(root->lchild), maxBiTreeDepth(root->rchild)) + 1 : 0;
}

//计算二叉树的总结点数
int numberOfBiTreeNodes(BiTree &tree) {
    if (tree == NULL)
        return 0;
    else {
        return 1 + numberOfBiTreeNodes(tree->lchild) + numberOfBiTreeNodes(tree->rchild);
    }
}

//前序遍历二叉树 biTree
Status PreOrderTraverse(BiTree biTree, Status (*Visit)(TElemType e)) {

    //采用二叉链表存储结构，Visit 是对数据元素操作的应用函数
    //先序遍历二叉树 biTree 的递归算法，对每个数据元素调用函数 Visit

    //调用实例：PreOrderTraverse (biTree, PrintElement);
    if (biTree) {
        if (Visit(biTree->data))
            if (PreOrderTraverse(biTree->lchild, Visit))
                if (PreOrderTraverse(biTree->rchild, Visit))
                    return OK;
        return ERROR;
    } else return OK;

}// PreOrderTraverse

//中序遍历二叉树 biTree
Status InOrderTraverse(BiTree biTree, Status (*Visit)(TElemType e)) {
    if (!biTree) {
        return OK;
    }

    InOrderTraverse(biTree->lchild, Visit);
    Visit(biTree->data);
    InOrderTraverse(biTree->rchild, Visit);
    return OK;
}

//后序遍历二叉树 biTree
Status PostOrderTraverse(BiTree biTree, Status (*Visit)(TElemType e)) {
    if (!biTree) {
        return OK;
    }

    PostOrderTraverse(biTree->lchild, Visit);
    PostOrderTraverse(biTree->rchild, Visit);
    Visit(biTree->data);
    return OK;
}


//层序遍历一个二叉链表(使用队列)
Status LevelOrderTraverse(BiTree biTree, Status (*visit)(TElemType e)) {
    LinkQueue linkQueue;
    InitQueue(linkQueue);
    BiTree tmpBiTreePointer = biTree;
    if (tmpBiTreePointer) {
        EnQueue(linkQueue, tmpBiTreePointer);
        while (!QueueEmpty(linkQueue)) {
            DeQueue(linkQueue, tmpBiTreePointer); //对出队列的结点进行访问，因为是从左到右，所以队列中的结点也是按照顺序的
            if (!visit(tmpBiTreePointer->data)) {
                return ERROR;
            }
            if (tmpBiTreePointer->lchild) EnQueue(linkQueue, tmpBiTreePointer->lchild);    //将左孩子插入队列尾部
            if (tmpBiTreePointer->rchild) EnQueue(linkQueue, tmpBiTreePointer->rchild);    //将右孩子插入队列尾部
        }
    } else {
        return ERROR;
    }
    return OK;
}

#ifdef SELEMTYPE_BI_TREE

//中序遍历(非递归算法1)
Status InOrderTraverseWithoutRecursion1(BiTree biTree, Status  (*Visit)(TElemType e)) {

    //采用二叉链表存储结构，Visit 是对数据元素操作的应用函数。
    //中序遍历二叉树 biTree 的非递归算法，对毎个数据元素调用函数 Visit。

    SqStack stack;
    SElemType tempEle;

    InitStack(stack);
    Push(stack, biTree);                                //根指针进找

    while (!StackEmpty(stack)) {

        while (GetTop(stack, tempEle) && tempEle)       //如果栈顶元素不为空，则把栈顶的左孩子放到栈顶，那么下次取的时候就是这个孩子，依次类推，从而向左走到尽头
            Push(stack, tempEle->lchild);

        Pop(stack, tempEle);                        //空指针退栈

        if (!StackEmpty(stack)) {                          //访问结点，向右一步
            Pop(stack, tempEle);

            if (!Visit(tempEle->data))
                return ERROR;

            Push(stack, tempEle->rchild);
        }// if

    }// while
    return OK;
}//InOrderTraverse
#endif


#ifdef SELEMTYPE_BI_TREE

//中序遍历(非递归算法2)
Status InOrderTraverseWithoutRecursion2(BiTree biTree, Status (*Visit)(TElemType e)) {

    //采用二叉链表存储结构，Visit 是对数据元素操作的应用函数。
    //中序遍历二叉树 biTree 的非递归算法，对每个数据元素调用函数 Visit
    SqStack stack;
    SElemType tempEle;

    InitStack(stack);
    tempEle = biTree;

    while (tempEle || !StackEmpty(stack)) {
        if (tempEle) {                                     //根指针进栈，遍历左子树
            Push(stack, tempEle);
            tempEle = tempEle->lchild;
        } else {                                           //根指针退栈，访问根结点，遍历右子树
            Pop(stack, tempEle);
            if (!Visit(tempEle->data))
                return ERROR;
            tempEle = tempEle->rchild;
        }//else
    }//While

    return OK;
}//InOrderTraverse
#endif

//根据当前深度返回左边打印多少个 tab
string getLeftBlackStr(int biTreeDepth, int curDepth) {
    string temp;
    for (int i = 0; i < (biTreeDepth - curDepth); i++) {
        temp += "\t";
    }
    temp += "\t";
    return temp; //整体再往右一个 tab
}

//按层次打印二叉树各个结点，使用 lastRight 控制换行，使用 lastLeft 控制左边缩进
//待解决：两个结点重合问题？打印结点路径，这个空格算不对
void LevelOrderPrint(BiTree biTree) {

    int biTreeDepth = maxBiTreeDepth(biTree);
    int curDepth = 0; //当前的深度

    BiTree nlastLastLeft = biTree;
    BiTree nlastLastRight = biTree;
    BiTree lastLeft = biTree;
    BiTree lastRight = biTree;

    LinkQueue linkQueue;
    InitQueue(linkQueue);
    EnQueue(linkQueue, biTree);
    curDepth = 1;

    BiTree tmpBiTreePointer;

    while (!QueueEmpty(linkQueue)) {

        DeQueue(linkQueue, tmpBiTreePointer);

        if (tmpBiTreePointer == lastLeft) {
            string result = getLeftBlackStr(biTreeDepth, curDepth);
            cout << result;
        }

        printf("%c\t\t", tmpBiTreePointer->data);

        if (tmpBiTreePointer->lchild != NULL) {
            EnQueue(linkQueue, tmpBiTreePointer->lchild);
            nlastLastRight = tmpBiTreePointer->lchild;               //如果有左结点那么 nlast 就是 lchild 的地址
            nlastLastLeft = tmpBiTreePointer->lchild;
        }

        if (tmpBiTreePointer->rchild != NULL) {
            EnQueue(linkQueue, tmpBiTreePointer->rchild);
            nlastLastRight = tmpBiTreePointer->rchild;               //如果有右结点那么 nlast 就是 rchild 的地址
        }

        if (tmpBiTreePointer == lastRight) {                         //将 DeQueue() 得到的队头元素的地址 tmpBiTreePointer
            lastRight = nlastLastRight;                              //和之前的 nlast（即现在的 last) 对比，相等则换行
            printf("\n");
        }

        if (tmpBiTreePointer == lastLeft) {
            lastLeft = nlastLastLeft;
            curDepth += 1;
        }
    }
}